package com.sam.book;

/**
 * 二项队列
 * @param <T>
 */
public class BinomialQueue<T extends Comparable<? super T>> {
    private static final int DEAFAULT_TREES = 1;

    private int currentSize;
    private Node<T>[] theTrees;

    public BinomialQueue() {
    }
    public BinomialQueue(T t) {
    }

    public void insert(T t) {

    }

    public void merge(BinomialQueue<T> rhs) {
        if (this == rhs) {
            return;
        }
        currentSize += rhs.currentSize;
        if (currentSize > capactiy()) {
            int maxLength = Math.max(theTrees.length, rhs.theTrees.length);
            expandTheTrees(maxLength + 1);
        }
        Node<T> carry = null;
        for (int i = 0, j = 1; j <= currentSize; i++, j *= 2) {
            Node<T> t1 = theTrees[i];
            Node<T> t2 = i < rhs.theTrees.length ? rhs.theTrees[i] : null;
            int whichCase = t1 == null ? 0 : 1;
            whichCase += t2 == null ? 0 : 2;
            whichCase += carry == null ? 0 : 4;

            switch (whichCase) {
                case 0://no trees:
                    break;
                case 1://only this
                    break;
                case 2:
                    theTrees[i] = t2;
                    rhs.theTrees[i] = null;
                    carry = null;
                    break;
                case 3://this & rhs
                    carry = combineTrees(t1, t2);
                    theTrees[i] = rhs.theTrees[i] = null;
                    break;
                case 4://only carry
                    theTrees[i] = carry;
                    carry = null;
                    break;
                case 5://this & carry
                    carry = combineTrees(t1, carry);
                    theTrees[i] = null;
                    break;
                case 6://rhs & carry
                    carry = combineTrees(t2, carry);
                    rhs.theTrees[i] = null;
                    break;
                case 7:// ALL trees
                    theTrees[i] = carry;
                    carry = combineTrees(t1, t2);
                    rhs.theTrees[i] = null;
                    break;
            }
        }

        for (int i = 0; i < rhs.theTrees.length; i++) {
            rhs.theTrees[i] = null;
        }
        rhs.currentSize = 0;
    }

    public T findMin() {
        int minIndex = findMinIndex();
        return theTrees[minIndex].element;
    }

    public T deleteMin() {
        if (isEmpty()) {
            return null;
        }
        int minIndex = findMinIndex();
        T min = theTrees[minIndex].element;

        Node<T> deleteTree = theTrees[minIndex].firstChild;

        BinomialQueue<T> deleteQueue = new BinomialQueue<>();
        deleteQueue.expandTheTrees(minIndex + 1);

        deleteQueue.currentSize = (1 << minIndex) - 1;
        for (int i = minIndex - 1; i > 0; i--) {
            deleteQueue.theTrees[i] = deleteTree;
            deleteTree = deleteTree.nextSibling;
            deleteQueue.theTrees[i].nextSibling = null;
        }

        theTrees[minIndex] = null;
        currentSize -= deleteQueue.currentSize + 1;

        merge(deleteQueue);

        return min;
    }

    public boolean isEmpty() {
        return currentSize == 0;
    }

    public void makeEmpty() {
        for (int i = 0; i < theTrees.length; i++) {
            theTrees[i] = null;
        }
        currentSize = 0;
    }

    private int capactiy() {
        return (1 << theTrees.length) - 1;
    }

    private int findMinIndex() {
        int minIndex = 0;
        for (int i = 1; i < theTrees.length; i++) {
            theTrees[i] = null;
            if (theTrees[i].element.compareTo(theTrees[minIndex].element) < 0) {
                minIndex = i;
            }
        }
        return minIndex;
    }

    private void expandTheTrees(int newNumTrees) {

    }

    private Node<T> combineTrees(Node<T> t1, Node<T> t2) {
        Node<T> bigger, smaller;
        if (t1.element.compareTo(t2.element) > 0) {
            bigger = t1;
            smaller = t2;
        } else {
            bigger = t2;
            smaller = t1;
        }
        bigger.nextSibling = smaller.firstChild;
        smaller.firstChild = bigger;
        return smaller;
    }

    private static class Node<E> {
        E element;
        Node<E> firstChild;
        Node<E> nextSibling;

        Node(E e) {
            this(e, null, null);
        }

        Node(E element, Node<E> firstChild, Node<E> nextSibling) {
            this.element = element;
            this.firstChild = firstChild;
            this.nextSibling = nextSibling;
        }




    }


}

